package q215;

/**
 * 215. 数组中的第k大元素
 */
public class Solution {

    // 堆 负节点 i 左子节点 i * 2 + 1 右子节点 i * 2 + 2
    public int findKthLargest(int[] nums, int k) {
        initMaxHeap(nums);
        int r = 0;
        for (int i = 0; i < k; i++) {
            r = nums[0];
            nums[0] = Integer.MIN_VALUE;
            buildMaxHeap(nums, 0);
        }
        return r;
    }

    public void initMaxHeap(int[] nums) {
        for (int i = nums.length / 2; i >= 0; i--) {
            buildMaxHeap(nums, i);
        }
    }

    public void buildMaxHeap(int[] nums, int i) {
        // 左子节点
        int l = i * 2 + 1;
        // 右子节点
        int r = i * 2 + 2;

        int target = i;
        if (l < nums.length && nums[l] > nums[target]) {
            target = l;
        }
        if (r < nums.length && nums[r] > nums[target]) {
            target = r;
        }

        if (i != target) {
            int temp = nums[i];
            nums[i] = nums[target];
            nums[target] = temp;
            buildMaxHeap(nums, target);
        }
    }

    public static void main(String[] args) {
        int[] ints = {2,3,6,1,9,2};
        Solution solution = new Solution();
        int kthLargest = solution.findKthLargest(ints, 3);
        System.out.println(kthLargest);
    }

}
